#include <iostream>
#include <vector>
using namespace std;

const int N=1e4*3+4000;
const int M=100;

pair<int,int> master[M];

vector<pair<int,int>> son[M];
int dp[N];
int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		int v,p,q;
		cin>>v>>p>>q;
		if(!q)
		{
			master[i]={v,v*p};
		}
		else{
			son[q].push_back({v,v*p});
		}
	}
	
	for(int i=1;i<=m;i++)
	{

		for(int j=n;j>=0;j--)
		{
			for(int k=0;k<1<<son[i].size();k++)
			{
				int v=master[i].first;
				int w=master[i].second;
				for(int z=0;z<son[i].size();z++)
				{
					if(k>>z&1)
					{
						v+=son[i][z].first;
						w+=son[i][z].second;
					}
				}
				if(j>=v)
				{
					dp[j]=max(dp[j],dp[j-v]+w);
				}
			}
		}
	}
	
	cout<<dp[n]<<endl;
	
	return 0;
}
